
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1887. -- Spoj 3974 3974. Another Tree Problem -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1887: Spoj 3974 3974. Another Tree Problem</h2><span class=green>Time Limit: </span>1 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>87&nbsp;&nbsp;<span class=green>Solved: </span>32<br>[<a href='submitpage.php?id=1887'>Submit</a>][<a href='problemstatus.php?id=1887'>Status</a>][<a href='bbs.php?id=1887'>Discuss</a>]</center><h2>Description</h2><div class=content>As  you  are  bound  to  know  by  now,  a  tree  is  a  connected  graph
consisting  of N  vertices  and N&#8722;1 edges. Trees  also  have  the  property
of  there  being  exactly  a  single  unique path  between  any  pair  of 
vertices. 
You will be given a tree in which every edge is assigned a weight – 
a non negative integer. The weight of a path is the product of the
weights of all edges on the path. The weight of the tree is the sum of 
the  weights  of  all  paths  in  the  tree.  Paths  going  in  opposite
directions  (A  to  B  and  B  to  A)  are considered the same and, when 
calculating the weight of a tree, are counted only once. 
Write a program that, given a tree, calculates its weight modulo 1000000007. 
</div><h2>Input</h2><div class=content>The first line contains the integer N (2 ≤ N ≤ 100 000), the number of vertices
in the tree. The vertices are numbered 1 to N. Each  of  the  following N&#8722;1
contains  three  integers A,  B  and W  (1 ≤ A,  B ≤ N,  0 ≤ W ≤  1000) 
describing one edge. The edge connects vertices A and B, and its weight is W.

</div><h2>Output</h2><div class=content>Output the weight of the tree, modulo 1000000007. 

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata><br />
3 <br />
3 2 100 <br />
2 1 100 <br />
 <br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
10200 <br />
</span></div><h2>HINT</h2>
			<div class=content><p>The weight of the path from 1 to 2 is 100 <br />
The weight of the path from 2 to 3 is 100 <br />
The weight of the path from 1 to 3 is 100 * 100 = 10000 <br />
So the weight of the tree is 10000 + 100 + 100 = 10200 </p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=1887'>Submit</a>][<a href='problemstatus.php?id=1887'>Status</a>][<a href='bbs.php?id=1887'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
